package com.yanceysong.codetop.s41_s50;


public class S48_Easy_69_x_的平方根 {
    /**
     * .S48_Easy_69_x_的平方根
     * .<p>
     * .LeetCode题号：<a href="https://leetcode.cn/problems/sqrtx/">69. x 的平方根</a>
     * .难度：简单
     * .核心标签：二分查找 / 数学 / 牛顿迭代
     * .<p>
     * .题目描述：给定一个非负整数 x，返回其算术平方根的向下取整（floor）。不允许使用库函数幂或开根号。
     * .<p>
     * .示例：
     * .输入：x = 4  输出：2 （2*2=4）
     * .输入：x = 8  输出：2 （sqrt(8)=2.828.. 取整 2）
     * .输入：x = 1  输出：1
     * .输入：x = 0  输出：0
     * .输入：x = 2147395600 输出：46340 （46340^2=2147395600，46341^2 溢出 int 范围）
     * .<p>
     * .输入约束：0 <= x <= 2^31 - 1
     * .输出要求：返回一个 int，满足 k^2 <= x < (k+1)^2
     * .<p>
     * .关键洞察：整数平方根的本质是“在有序区间中寻找满足 k^2 <= x 的最大 k”，是典型的单调性判定 → 可用二分。也可用牛顿迭代快速逼近根。
     * .<p>
     * .解法对比：
     * .1. 线性扫描：O(sqrt(x))，在 x 很大时低效 → 放弃。
     * .2. 二分查找：O(log x)，稳定易实现，溢出易控。
     * .3. 牛顿迭代：O(log x)（迭代次数更少），需注意类型溢出与除法。
     * .<p>
     * .二分关键思路：区间 [0, x] （可优化为 [0, x/2 + 1]）中，检查 mid^2 与 x 的关系：
     * .- 若 mid^2 <= x：mid 为一个“可行解”，尝试右移扩大（保留答案记录）
     * .- 若 mid^2 > x：mid 过大，收缩右边界
     * .最终记录的最大“可行解”即 floor(sqrt(x))。
     * .<p>
     * .ASCII 流程演示（x=27）：
     * .初始：low=0, high=27
     * .mid=13 → 13^2=169>27 → high=12
     * .mid=6  → 36>27 → high=5
     * .mid=2  → 4<=27  → ans=2, low=3
     * .mid=4  → 16<=27 → ans=4, low=5
     * .mid=5  → 25<=27 → ans=5, low=6
     * .low(6) > high(5) 结束，返回 5
     * .<p>
     * .另一示例（x=8）：
     * .low=0 high=8 mid=4 → 16>8 high=3
     * .mid=1 → 1<=8 ans=1 low=2
     * .mid=2 → 4<=8 ans=2 low=3
     * .mid=3 → 9>8 high=2 => 结束 ans=2
     * .<p>
     * .为什么必须用 long 检查 mid^2：防止 mid 在接近 46341 时乘法溢出 int 范围。
     * .<p>
     * .Mermaid 文本图：
     * .graph TD
     * .  A[初始化 low=0 high=x answer=-1] --> B{low <= high?}
     * .  B -->|是| C[计算 mid]
     * .  C --> D{mid^2 <= x?}
     * .  D -->|是| E[answer=mid; low=mid+1]
     * .  D -->|否| F[high=mid-1]
     * .  E --> G[回到循环]
     * .  F --> G[回到循环]
     * .  B -->|否| H[返回 answer]
     * .<p>
     * .复杂度：
     * .时间：O(log x)：每轮二分缩小一半区间
     * .空间：O(1)：仅使用常量变量
     * .<p>
     * .进阶（牛顿法）公式：r_{n+1} = (r_n + x / r_n) / 2，快速收敛到 sqrt(x)，迭代次数少。
     * .<p>
     * .测试策略：
     * .- 基础：常规数字 (4,8,10)
     * .- 边界：0,1
     * .- 完全平方：16, 2147395600
     * .- 最大值：Integer.MAX_VALUE
     * .- 一致性：比对二分与牛顿实现
     * .- 随机性：随机验证多组数据一致性
     */
    public int mySqrt(int x) {
        // === 早期返回（微优化）===
        if (x < 2) { // 0 ->0, 1 ->1
            return x;
        }
        // === 初始化阶段 ===
        int low = 0;                // 搜索区间左边界
        int high = x;               // 搜索区间右边界（可优化为 x/2+1，但保持语义直观）
        int floorSqrt = -1;         // 记录当前“满足 mid^2 <= x”的最大 mid

        // === 核心：二分查找 ===
        while (low <= high) {
            // 中点计算防止溢出
            int mid = low + (high - low) / 2;
            long midSquared = (long) mid * mid; // 使用 long 防止乘法溢出

            if (midSquared <= x) {
                // mid 是一个合法候选；更新记录并尝试向右扩展
                floorSqrt = mid;
                low = mid + 1;
            } else {
                // mid 过大，收缩右边界
                high = mid - 1;
            }
        }
        // === 结果阶段 ===
        return floorSqrt;
    }

    /**
     * .牛顿迭代实现：快速逼近平方根。
     * .原理：求 f(r)=r^2 - x 的根，迭代公式 r_{n+1} = (r_n + x / r_n)/2。
     */
    public int mySqrtNewton(int x) {
        if (x == 0) return 0;
        long estimate = x; // 使用 long 避免除法中间过程溢出
        while (estimate * estimate > x){ // 若当前估计的平方仍大于 x 则继续迭代
            estimate = (estimate + x / estimate) / 2; // 牛顿更新
        }
        return (int) estimate; // 向下取整
    }

    // ================= 分场景测试方法（模仿环形链表结构）=================

    // 基础功能测试
    private static void testBasicCases() {
        System.out.println("--- 测试1: 基础功能 ---");
        S48_Easy_69_x_的平方根 solver = new S48_Easy_69_x_的平方根();
        int[] inputs = {4, 8, 10, 2, 3, 5};
        for (int x : inputs) {
            int result = solver.mySqrt(x);
            System.out.printf("x=%d -> sqrt=%d%n", x, result);
        }
    }

    // 边界值测试
    private static void testBoundaryCases() {
        System.out.println("--- 测试2: 边界值 ---");
        S48_Easy_69_x_的平方根 solver = new S48_Easy_69_x_的平方根();
        int[] inputs = {0, 1};
        for (int x : inputs) {
            System.out.printf("x=%d -> sqrt=%d%n", x, solver.mySqrt(x));
        }
    }

    // 完全平方数测试
    private static void testPerfectSquares() {
        System.out.println("--- 测试3: 完全平方数 ---");
        S48_Easy_69_x_的平方根 solver = new S48_Easy_69_x_的平方根();
        int[] inputs = {1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 2147395600};
        for (int x : inputs) {
            int r = solver.mySqrt(x);
            System.out.printf("x=%d -> sqrt=%d 验证: %d^2=%d%n", x, r, r, (long) r *r);
        }
    }

    // 最大值与溢出临界测试
    private static void testMaxValue() {
        System.out.println("--- 测试4: 最大值临界 ---");
        S48_Easy_69_x_的平方根 solver = new S48_Easy_69_x_的平方根();
        int x = Integer.MAX_VALUE;
        int r = solver.mySqrt(x);
        System.out.printf("x=%d -> sqrt=%d 验证: %d^2=%d <= %d%n", x, r, r, (long) r *r, (long) x);
    }

    // 二分与牛顿结果一致性测试
    private static void testNewtonConsistency() {
        System.out.println("--- 测试5: 二分 vs 牛顿一致性 ---");
        S48_Easy_69_x_的平方根 solver = new S48_Easy_69_x_的平方根();
        int[] samples = {0, 1, 2, 3, 8, 15, 99, 100, 121, 2147395600, Integer.MAX_VALUE};
        for (int x : samples) {
            int a = solver.mySqrt(x);
            int b = solver.mySqrtNewton(x);
            System.out.printf("x=%d -> 二分=%d 牛顿=%d %s%n", x, a, b, (a == b ? "✓" : "✗"));
        }
    }

    // 随机数据正确性与一致性测试（小规模）
    private static void testRandomSamples() {
        System.out.println("--- 测试6: 随机一致性 (展示前30个) ---");
        S48_Easy_69_x_的平方根 solver = new S48_Easy_69_x_的平方根();
        int count = 30;
        java.util.Random rand = new java.util.Random(42);
        for (int i = 0; i < count; i++) {
            int x = rand.nextInt(Integer.MAX_VALUE); // 随机非负数
            int a = solver.mySqrt(x);
            int b = solver.mySqrtNewton(x);
            if (a != b) {
                System.out.printf("不一致: x=%d 二分=%d 牛顿=%d%n", x, a, b);
                throw new AssertionError("随机样本不一致");
            }
            if (i < 10) { // 控制输出量
                System.out.printf("x=%d -> sqrt=%d%n", x, a);
            }
        }
        System.out.println("随机样本全部一致 ✔");
    }

    // 回归验证：大量连续值（只抽样打印）
    private static void testSequentialRange() {
        System.out.println("--- 测试7: 连续区间抽样 [0..500] ---");
        S48_Easy_69_x_的平方根 solver = new S48_Easy_69_x_的平方根();
        for (int x = 0; x <= 500; x++) {
            int r = solver.mySqrt(x);
            // 验证 r^2 <= x < (r+1)^2
            long r2 = (long) r * r;
            long next2 = (long) (r + 1) * (r + 1);
            if (!(r2 <= x && x < next2)) {
                throw new AssertionError("区间验证失败 x=" + x + " r=" + r);
            }
            if (x % 60 == 0) { // 抽样打印
                System.out.printf("x=%d -> sqrt=%d%n", x, r);
            }
        }
        System.out.println("区间验证通过 ✔");
    }

    // ================= 主函数 =================
    public static void main(String[] args) {
        System.out.println("=== x 的平方根 测试开始 ===\n");
        testBasicCases();
        System.out.println();
        testBoundaryCases();
        System.out.println();
        testPerfectSquares();
        System.out.println();
        testMaxValue();
        System.out.println();
        testNewtonConsistency();
        System.out.println();
        testRandomSamples();
        System.out.println();
        testSequentialRange();
        System.out.println();
        System.out.println("=== 所有测试完成 ===");
    }
}
